/*
 * @Author: long-xinyu2 2192763423@qq.com
 * @Date: 2025-06-08 17:45:01
 * @LastEditors: long-xinyu2 2192763423@qq.com
 * @LastEditTime: 2025-06-08 17:45:17
 * @FilePath: \algorithm-training\leetcode\5. 最长回文子串.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        int ans = 0;
        int maxlen = 1;
        int begin = 0;
        vector<vector<bool>> arr(len + 10,vector<bool>(len + 10));
        for(int i = 0; i < len; i ++)
        {
            arr[i][i] = true;
        }
        for(int k = 2; k <= len; k ++)
        {
            for(int i = 0; i <= len - 1; i ++)
            {
                int j = i + k - 1;
                if(j >= len) break;
                if(s[i] != s[j])
                {
                    arr[i][j] = false;
                }
                else
                {
                    if(j - i < 3) arr[i][j] = true; 
                    else arr[i][j] = arr[i + 1][j - 1];
                }
                if(arr[i][j] && j - i + 1 > maxlen)
                {
                    maxlen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substr(begin,maxlen);
    }
};